#ifndef _GREEDY_
#define _GREEDY_

#include <iostream>
#include <vector>
using namespace std;

class Greedy {

public:
    Greedy() {}
    ~Greedy() {}
    /* 334. 递增的三元子序列
       贪心思想是：为了找到递增的三元子序列，one 和 two 应该尽可能地小，此时找到递增的三元子序列的可能性更大。 
       two附带隐含信息 —— 这之前有个数比two小 所以此时找到的递增子序列不是one、two、three的1 5 6，而是old one、two、three的2 5 6。*/
    bool increasingTriplet( const vector< int >& nums ) {

        if ( nums.size() <= 2 ) {
            return false;
        }

        int one = INT32_MAX;
        int two = INT32_MAX; 

        for ( int i = 0; i < nums.size(); i++ ) {
            if ( nums[ i ] > two && one != two ) {
                return true;
            }
            else if ( nums[ i ] > one && nums[ i ] < two ) {
                two = nums[ i ];
            }
            else if ( nums[ i ] < one ) {
                one = nums[ i ];
            }
        }
        return false;
    }
};

#endif /* _GREEDY_ */